{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Good Base"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestGoodBase"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小好进制"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>以字符串的形式给出 <code>n</code>&nbsp;, 以字符串的形式返回<em> <code>n</code> 的最小 <strong>好进制</strong> </em>&nbsp;。</p>\n",
    "\n",
    "<p>如果 <code>n</code> 的 &nbsp;<code>k(k&gt;=2)</code>&nbsp;进制数的所有数位全为1，则称&nbsp;<code>k(k&gt;=2)</code>&nbsp;是 <code>n</code> 的一个&nbsp;<strong>好进制&nbsp;</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = \"13\"\n",
    "<strong>输出：</strong>\"3\"\n",
    "<strong>解释：</strong>13 的 3 进制是 111。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = \"4681\"\n",
    "<strong>输出：</strong>\"8\"\n",
    "<strong>解释：</strong>4681 的 8 进制是 11111。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = \"1000000000000000000\"\n",
    "<strong>输出：</strong>\"999999999999999999\"\n",
    "<strong>解释：</strong>1000000000000000000 的 999999999999999999 进制是 11。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n</code> 的取值范围是&nbsp;<code>[3, 10<sup>18</sup>]</code></li>\n",
    "\t<li><code>n</code> 没有前导 0</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-good-base](https://leetcode.cn/problems/smallest-good-base/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-good-base](https://leetcode.cn/problems/smallest-good-base/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"13\"', '\"4681\"', '\"1000000000000000000\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        num = int(n)\n",
    "        # n = x^(m-1) + x^(m-2) + ... + x + 1\n",
    "        for m in range(num.bit_length(),2,-1):\n",
    "            # 二项式展开 x^(m-1) < n < (x+1)^(m-1)\n",
    "            x = int(pow(num,1/(m-1)))\n",
    "            # 等比数列求和 n = (x^m - 1)/(x-1)\n",
    "            if num == (pow(x,m) - 1)//(x-1):\n",
    "                return str(x)\n",
    "        return str(num-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        import math\n",
    "\n",
    "        def check(k, l, n):\n",
    "            res = 0\n",
    "            rawK = k\n",
    "            k = 1\n",
    "            for i in range(l):\n",
    "                res += k\n",
    "                k *= rawK\n",
    "            if res < int(n):\n",
    "                return -1\n",
    "            elif res > int(n):\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        for l in range(60, 0, -1):\n",
    "            left = 2\n",
    "            right = int(n)\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                res = check(mid, l, n)\n",
    "                if res < 0:\n",
    "                    left = mid + 1\n",
    "                elif res > 0:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    return str(mid)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        n=int(n)\n",
    "        m=len(bin(n))-2\n",
    "        def int2(s,t):\n",
    "            res=0\n",
    "            for i in range(len(s)):res+=t**i\n",
    "            return res\n",
    "        def help(l):\n",
    "            s='1'*l\n",
    "            lo,hi=2,n\n",
    "            while lo<=hi:\n",
    "                mid=(lo+hi)//2\n",
    "                t=int2(s,mid)\n",
    "                if t==n:return mid\n",
    "                elif t>n:hi=mid-1\n",
    "                else:lo=mid+1\n",
    "            return -1\n",
    "        for i in range(m,1,-1):\n",
    "            t=help(i)\n",
    "            if t!=-1:return str(t)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        import math \n",
    "        max_p  = int(math.log(int(n),2)) # 如果用for循环对幂次p从1开始到n，肯定超时。这里能想到。\n",
    "        for p in range(max_p,0,-1):\n",
    "            k = int(pow(int(n),1.0/p))  # 对k的范围确定，如果同样从1开始到n，肯定超时，这里想不到。\n",
    "            #value = (pow(k,p+1)-1)/(k-1) # 如果用等比数列求和公式，肯定造成溢出，导致错误。\n",
    "           \n",
    "           ####  下面是计算等比数列求和\n",
    "            sum_value = 1\n",
    "            mul = 1\n",
    "            for i in range(1,p+1): # 等比数列求和\n",
    "                mul*=k\n",
    "                sum_value+=mul\n",
    "\n",
    "           #  如果求和结果等于n，则直接返回str(k)\n",
    "            if sum_value==int(n):\n",
    "                return str(k)\n",
    "        # 如果不满足上述要求，直接返回最大的k: 即 n-1\n",
    "        return str(int(n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n) -> str:\n",
    "        n = int(n)\n",
    "        #p^x\n",
    "        def cal(p, x):\n",
    "            ans = 0\n",
    "            cur = 1\n",
    "            for i in range(x):\n",
    "                ans += cur\n",
    "                cur *= p\n",
    "            return ans\n",
    "        for i in range(63, 0, -1):\n",
    "            l = 2\n",
    "            r = 0x3f3f3f3f3f3f3f3f\n",
    "            a = -1\n",
    "            while l <= r:\n",
    "                mid = l + (r - l) // 2\n",
    "                cur = cal(mid, i)\n",
    "                if cur >= n:\n",
    "                    r = mid - 1\n",
    "                    if cur == n:\n",
    "                        a = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if a != -1:\n",
    "                return str(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        n=int(n)\n",
    "        def sum_with(base,N):\n",
    "            return (1-base**N)//(1-base)\n",
    "        for N in range(len(bin(n))-2,0,-1):\n",
    "            l=2\n",
    "            r=n-1\n",
    "            while l <=r:\n",
    "                mid=(l+r)//2\n",
    "                v=sum_with(mid, N)\n",
    "\n",
    "                if v<n:\n",
    "                    l=mid+1\n",
    "                elif v>n:\n",
    "                    r=mid-1\n",
    "                else:\n",
    "                    return str(mid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        num = int(n)\n",
    "        # n = x^(m-1) + x^(m-2) + ... + x + 1\n",
    "        for m in range(num.bit_length(),2,-1):\n",
    "            # 二项式展开 x^(m-1) < n < (x+1)^(m-1)\n",
    "            x = int(pow(num,1/(m-1)))\n",
    "            # 等比数列求和 n = (x^m - 1)/(x-1)\n",
    "            if num == (pow(x,m) - 1)//(x-1):\n",
    "                return str(x)\n",
    "        return str(num-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        num = int(n)\n",
    "        for m in range(num.bit_length(), 2, -1):\n",
    "            x = int(pow(num, 1 / (m - 1)))\n",
    "            if num == (pow(x, m) - 1) // (x - 1):\n",
    "                return str(x)\n",
    "        return str(num - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestGoodBase(self, n: str) -> str:\r\n",
    "        # assume that under k-base, n is presented as m \"1\"s\r\n",
    "        # m is decreasing according to k\r\n",
    "        # as 2 ** 60 - 1 > 10 ** 18 >= n, we have m < 60\r\n",
    "        # under n-1 base, n is always \"11\", i.e. m = 2\r\n",
    "        # therefore we are looking for the largest m, 2 <= m < 60\r\n",
    "        # such that n = m \"1\"s\r\n",
    "        # we could binary search for given m, that the smallest k\r\n",
    "        # where under k-base, m \"1\"s >= n\r\n",
    "        n = int(n)\r\n",
    "\r\n",
    "        def check(m: int) -> int:\r\n",
    "            lo = 2\r\n",
    "            hi = n - 1\r\n",
    "            while lo < hi:\r\n",
    "                mid = lo + hi >> 1\r\n",
    "                # m \"1\" under mid base\r\n",
    "                num = sum(mid ** i for i in range(m))\r\n",
    "                if num >= n:\r\n",
    "                    hi = mid\r\n",
    "                else:\r\n",
    "                    lo = mid + 1\r\n",
    "\r\n",
    "            return lo\r\n",
    "        \r\n",
    "        res = n - 1\r\n",
    "        for m in range(59, 1, -1):\r\n",
    "            res = check(m)\r\n",
    "            if n == sum(res ** i for i in range(m)):\r\n",
    "                break\r\n",
    "        \r\n",
    "        return str(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:    \n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        n = int(n)\n",
    "        maxpow = int(math.log(n,2))\n",
    "        \n",
    "        for power_num in range(maxpow, 1, -1):\n",
    "            k = int(n ** (1/power_num))\n",
    "            if (k**(power_num+1)-1)//(k-1) == n:\n",
    "                return str(k)\n",
    "        return str(n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        n = int(n)\n",
    "        m = int(math.log(n,2))\n",
    "        for i in range(m,1,-1):\n",
    "            k = int(n ** (1/i))\n",
    "            if n * (k-1) == k ** (i+1) - 1:\n",
    "                return str(k)\n",
    "        return str(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "\n",
    "        def binary_search(k, n):\n",
    "            \n",
    "            left, right = 2, n\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                tmp = sum([mid**i for i in range(k)])\n",
    "                if tmp > n:\n",
    "                    right = mid\n",
    "                elif tmp < n:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    return True, mid\n",
    "            return False, None\n",
    "\n",
    "        num = int(n)\n",
    "        MAX = min(60, int(math.log2(num + 1)))\n",
    "        for k in range(MAX, 1, -1):\n",
    "            flag, ans = binary_search(k, num)\n",
    "            if flag:\n",
    "                return str(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        n = int(n)\n",
    "        def check(m, k):\n",
    "            ans = 0\n",
    "            for i in range(k):\n",
    "                ans = ans * m + 1\n",
    "            return ans\n",
    "        k = n\n",
    "        for length in range(2, 65): \n",
    "            i = 2 \n",
    "            j = n - 1 \n",
    "            while i <= j: \n",
    "                mid = (i + j) // 2 \n",
    "                tmp = check(mid, length) \n",
    "                if tmp == n: \n",
    "                    if k > mid: \n",
    "                        k = mid \n",
    "                    break \n",
    "                elif tmp < n: \n",
    "                    i = mid + 1 \n",
    "                else: \n",
    "                    j = mid - 1 \n",
    "        return str(k)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 数学\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        num = int(n)\n",
    "        # 枚举 k进制 中 1 的个数，最多为 二进制 时的位数\n",
    "        for i in range(num.bit_length(), 2, -1):\n",
    "            # k^0 + k^1 + …… + k^(i-1) = n -- 解方程计算 k\n",
    "            # k < n^(1/(i - 1)) < k +1\n",
    "            k = int(pow(num, 1 / (i - 1)))\n",
    "            # 检查 k 进制数 (11…11) (i个1)是否是n\n",
    "            if num == (pow(k, i) - 1) // (k - 1):\n",
    "                return str(k)\n",
    "        return str(num - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        # k^8 - 1 = (k - 1)*n\n",
    "        # k表示k进制，s表示k禁止下11...11长度，k尽量小，则s尽量大，由大到小枚举s, 计算对应k的值\n",
    "        num = int(n)\n",
    "        # 枚举k进制中1的个数，最多为二进制时的位数\n",
    "        for i in range(num.bit_length(), 2, -1):\n",
    "            # k^0 + k^1 + ... + k^(i-1) = n ——通过二分法计算k\n",
    "            # kn - n = k^i - 1\n",
    "            left = 2\n",
    "            right = num - 1\n",
    "            while left <= right:\n",
    "                mid = (left+right)//2\n",
    "                s = mid * num - num - pow(mid, i) + 1\n",
    "                if s == 0:\n",
    "                    return str(mid)\n",
    "                elif s > 0:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "        return str(num - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import log\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        def solve(n, t):      # res = solve(13, 4)\n",
    "            lo = 2            \n",
    "            hi = int(n ** (1/(t-1))) + 1  # hi = int(13 ** (1/3)) + 1 = 3\n",
    "            while lo + 1 < hi:  \n",
    "                k = (lo + hi) // 2\n",
    "                up = pow(k, t) - 1\n",
    "                down = k - 1\n",
    "                res = down * n \n",
    "                if res > up:\n",
    "                    lo = k\n",
    "                elif res < up:\n",
    "                    hi = k\n",
    "                else:\n",
    "                    return k\n",
    "            up = pow(lo, t) - 1   # up = pow(2, 4) - 1 = 15\n",
    "            down = lo - 1         # down = 2 - 1 = 1\n",
    "            if up == down * n:    \n",
    "                return lo\n",
    "            up = pow(hi, t) - 1   # up = pow(3, 4) - 1 = 80\n",
    "            down = hi - 1         # down = 2\n",
    "            if up == down * n:    #\n",
    "                return hi\n",
    "            return -1\n",
    "\n",
    "        n = int(n)   # n = 13\n",
    "        for t in range(int(log(n, 2))+1, 1, -1):   # t = 4->2\n",
    "            res = solve(n, t)     # res = solve(13, 4)\n",
    "            if res > -1:\n",
    "                return str(res)\n",
    "        return str(n-1)           # \"3\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        num = int(n)\n",
    "        for m in range(num.bit_length(),2,-1):\n",
    "            x = int(pow(num,1/(m-1)))\n",
    "            if num == (pow(x,m) - 1)//(x-1):\n",
    "                return str(x)\n",
    "        return str(num-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import ceil\n",
    "\n",
    "\n",
    "def f(x, n, m):\n",
    "    return x**m - n * x + n - 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        n = int(n)\n",
    "        ans = n - 1\n",
    "        for m in range(2, 65):\n",
    "            x0 = (n / (m - 1))**(1 / (m - 1))\n",
    "            lf, rf = 2, x0\n",
    "            while lf <= rf:\n",
    "                cf = (lf + rf) // 2\n",
    "                v = f(cf, n, m)\n",
    "                if v == 0:\n",
    "                    ans = min(ans, cf)\n",
    "                    break\n",
    "                elif v > 0:\n",
    "                    lf = cf + 1\n",
    "                else:\n",
    "                    rf = cf - 1\n",
    "            lf, rf = max(2, ceil(x0)), n - 1\n",
    "            while lf <= rf:\n",
    "                cf = (lf + rf) // 2\n",
    "                v = f(cf, n, m)\n",
    "                if v == 0:\n",
    "                    ans = min(ans, cf)\n",
    "                    break\n",
    "                elif v < 0:\n",
    "                    lf = cf + 1\n",
    "                else:\n",
    "                    rf = cf - 1\n",
    "        return str(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        #copy 二分\n",
    "        num  = int(n)\n",
    "\n",
    "        for i in range(num.bit_length(),2,-1):\n",
    "            left , right = 2,num-1\n",
    "            while left<= right:\n",
    "                mid = (left+right)//2\n",
    "                s= mid*num -num -pow(mid,i)+1\n",
    "                if s ==0:\n",
    "                    return str(mid)\n",
    "                elif s >0:\n",
    "                    left= mid +1\n",
    "                else:\n",
    "                    right = mid -1\n",
    "        return str(num-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        num = int(n)\n",
    "        # 枚举 k进制 中 1 的个数，最多为 二进制 时的位数\n",
    "        for i in range(num.bit_length(), 2, -1):\n",
    "            # k^0 + k^1 + …… + k^(i-1) = n -- 通过二分法计算 k\n",
    "            # kn - n = k^i - 1\n",
    "            left, right = 2, num - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                s = mid * num - num - pow(mid, i) + 1\n",
    "                if s == 0:\n",
    "                    return str(mid)\n",
    "                elif s > 0:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "        return str(num - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        n=int(n)\n",
    "        def check(b, s):\n",
    "            ans=0\n",
    "            for i in range(s+1):\n",
    "                ans+=b**i\n",
    "            return ans==n\n",
    "\n",
    "        for s in range(59, 1, -1): # s+1位的二进制\n",
    "            b = int(n ** (1 / s))\n",
    "            if b>1 and check(b,s):\n",
    "                return str(b)\n",
    "        return str(n - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 数学\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        num = int(n)\n",
    "        # 枚举 k进制 中 1 的个数，最多为 二进制 时的位数\n",
    "        for i in range(num.bit_length(), 2, -1):\n",
    "            # k^0 + k^1 + …… + k^(i-1) = n -- 解方程计算 k\n",
    "            # k < n^(1/(i - 1)) < k +1\n",
    "            k = int(pow(num, 1 / (i - 1)))\n",
    "            # 检查 k 进制数 (11…11) (i个1)是否是n\n",
    "            if num == (pow(k, i) - 1) // (k - 1):\n",
    "                return str(k)\n",
    "        return str(num - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        num = int(n)\n",
    "        for i in range(num.bit_length(), 2, -1):\n",
    "            k = int(pow(num, 1 / (i - 1)))\n",
    "            if num == (pow(k, i) - 1) // (k - 1):\n",
    "                return str(k)\n",
    "        return str(num - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        num = int(n)\n",
    "\n",
    "        def check(kk:int,cnt:int)->int:\n",
    "            s=0\n",
    "            for i in range(0,cnt):\n",
    "                s=s*kk+1\n",
    "            return s\n",
    "\n",
    "        #本题可以使用枚举+二分的方法，由于n最大为1e18，换成最小的二进制也就有64个连续的1，所以进制越大连续的1越短，所以我们可以枚举1个个数，然后我们可以使用二分来查找进制k,k越大最终得到的数也就越大，反之k越小最终得到的数也就越小，满足“递增性”,遍历完1的个数，得到最小的进制k既可。\n",
    "        ans=1e18\n",
    "        for i in range(1,64):\n",
    "            l=2\n",
    "            r=num\n",
    "            while l<=r:\n",
    "                k=l+r>>1\n",
    "                x=check(k,i)\n",
    "                if x==num:\n",
    "                    ans=min(ans,k)\n",
    "                    break\n",
    "                elif x < num:\n",
    "                    l=k+1\n",
    "                else:\n",
    "                    r=k-1\n",
    "\n",
    "        return str(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 数学\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        num = int(n)\n",
    "        # 枚举 k进制 中 1 的个数，最多为 二进制 时的位数\n",
    "        for i in range(num.bit_length(), 2, -1):\n",
    "            # k^0 + k^1 + …… + k^(i-1) = n -- 解方程计算 k\n",
    "            # k < n^(1/(i - 1)) < k +1\n",
    "            k = int(pow(num, 1 / (i - 1)))\n",
    "            # 检查 k 进制数 (11…11) (i个1)是否是n\n",
    "            if num == (pow(k, i) - 1) // (k - 1):\n",
    "                return str(k)\n",
    "        return str(num - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        n = int(n)\n",
    "        def f(b, k):\n",
    "            return (b ** k - 1) // (b - 1)\n",
    "        for k in range(60, 1, -1):\n",
    "            b = bisect_left(range(n), n, key=lambda b: f(b + 2, k)) + 2\n",
    "            if f(b, k) == n:\n",
    "                return str(b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestGoodBase(self, n: str) -> str:\n",
    "        n  = int(n)\n",
    "        def sum_with(base,n):\n",
    "            return (1-base**n)//(1-base)\n",
    "        for N in range(len(bin(n))-2,0,-1):\n",
    "            l =2\n",
    "            r = n-1\n",
    "            while(l<=r):\n",
    "                mid = (l+r)//2\n",
    "                v = sum_with(mid,N)\n",
    "                if v<n: l = mid+1\n",
    "                elif v>n:\n",
    "                    r = mid -1 \n",
    "                else:\n",
    "                    return str(mid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "class Solution:\r\n",
    "    def smallestGoodBase(self, n: str) -> str:\r\n",
    "        N=int(n)\r\n",
    "        maxM=int(math.log2(N))\r\n",
    "        for m in range(maxM,0,-1):\r\n",
    "            k=int(math.pow(N,1/m))\r\n",
    "            if k<=1:\r\n",
    "                continue\r\n",
    "            base=1\r\n",
    "            s=0\r\n",
    "            for i in range(m+1):\r\n",
    "                s+=base\r\n",
    "                base*=k\r\n",
    "            if s==N:\r\n",
    "                return str(k)\r\n",
    "        return str(N-1)\r\n",
    "\r\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
